package com.cat.gridChart;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/k-highest-ranked-items-within-a-price-range/
 * @create 2025/9/8 11:05
 * @since JDK17
 */

public class Solution17 {
    List<List<Integer>> ans;
    static int[][] g, q = new int[100010][2], d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int h, t, low, high, n, m;
    boolean[][] vis;

    Comparator<List<Integer>> comparator = (o1, o2) -> {
        int a = o1.get(0), b = o1.get(1), c = o2.get(0), d = o2.get(1);
        if (g[a][b] != g[c][d]) {
            return g[a][b] - g[c][d];
        } else if (a != c) {
            return a - c;
        } else {
            return b - d;
        }
    };

    void bfs(int k) {
        while (h < t && k > 0) {
            List<List<Integer>> list = new ArrayList<>();
            int cnt = 0;
            for (int end = t; h < end; h++) {
                var p = q[h];
                for (int i = 0; i < 4; i++) {
                    int nx = p[0] + d[i][0], ny = p[1] + d[i][1];
                    if (nx == -1 || nx == n || ny == -1 || ny == m || vis[nx][ny] || g[nx][ny] == 0) {
                        continue;
                    }
                    vis[nx][ny] = true;
                    q[t++] = new int[]{nx, ny};
                    if (g[nx][ny] >= low && g[nx][ny] <= high) {
                        list.add(new ArrayList<>(Arrays.asList(nx, ny)));
                        cnt++;
                    }

                }
            }
            if (cnt <= k) {
                list.sort(comparator);
                ans.addAll(list);
                k -= cnt;
            } else {
                list.sort(comparator);
                for (int i = 0; i < k; i++) {
                    ans.add(list.get(i));
                }
                k = 0;
            }
        }
    }


    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        ans = new ArrayList<>();
        low = pricing[0];
        high = pricing[1];
        n = grid.length;
        m = grid[0].length;
        vis = new boolean[n][m];
        g = grid;
        q[t++] = start;
        vis[start[0]][start[1]] = true;
        if (g[start[0]][start[1]] >= low && g[start[0]][start[1]] <= high) {
            ans.add(new ArrayList<>(Arrays.asList(start[0], start[1])));
            k--;
        }
        bfs(k);
        return ans;
    }
}
